0%

Self-Learned Algorithms - 09

Posted on In

Self-Learned Algorithms - 09

This is my learning note about algorithms.

Reference

875.爱吃香蕉的珂珂

https://leetcode-cn.com/problems/koko-eating-bananas/

题解

  • 看完题目最大的感想：珂珂真能吃，警卫真能摸……

解法

  • 二分法：找到一个最小的K，此时小于K的都不满足条件，而大于K的都是满足条件的
1
2
3
4
5
6
7
8
9
10
11
def possible(K):
	return sum((p-1) // K + 1 for p in piles) <= H

lo, hi = 1, max(piles) # 或从[min(piles),max(piles)]二分
while lo < hi:
  mi = (lo + hi) // 2
  if not possible(mi):
  	lo = mi + 1
  else:
  	hi = mi
return lo
1
2
3
4
5
i = math.ceil(sum(piles) / H)
while True:
  if sum(math.ceil(p / i) for p in piles) <= H:
  	return i
  i += 1

69.x的平方根

https://leetcode-cn.com/problems/sqrtx/

题解

  • 暴力解法不可取

解法

  • 二分法：右边界用x本身是可以的，另外除了0、1、2、3、4之外，其他数字的平方根都不会大于等于它的二分之一，也可以重新考虑一下边界问题
1
2
3
4
5
6
7
8
9
l, r, ans = 0, x, -1
while l <= r:
  mid = (l + r) // 2
  if mid * mid <= x:
    ans = mid
    l = mid + 1
  else:
    r = mid - 1
return ans
1
2
3
4
5
6
7
8
9
10
if x == 0:
	return 0

C, x0 = float(x), float(x)
while True:
  xi = 0.5 * (x0 + C / x0)
  if abs(x0 - xi) < 1e-7:
  	break
  x0 = xi
return int(x0)

278.第一个错误的版本

https://leetcode-cn.com/problems/first-bad-version/

解法

  • 二分法：返回的条件为当前版本为True且（当前索引为0 或 左边的版本为False）。m * 的作用是避免 m - 1 为负数，如果 m 为 0，则代表左边没有版本，只需判断当前版本是否为 True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
l, h = 1, n
while l <= h:
  m = (l + h) // 2
  # 感觉判断不太一样？
  if isBadVersion(m) > m * isBadVersion(m - 1):
  	return m
  elif isBadVersion(m):
  	h = m - 1
  else:
  	l = m + 1
    
  # 更加正常一点的判断？但是居然超时了
  if isBadVersion(m):
    h = m
  else:
    l = m + 1
return l